In packet networks, packets are not guaranteed to arrive in the same order that they were sent, and so certain nodes on the packet network must be able to process and reassemble packets regardless of the order received. Individual packets may be likewise fragmented, and a node on the packet network must be able to reassemble the packet fragments correctly regardless of the order that the fragments are received. To test this capability, it is desirable to provide randomly shuffled packets or packet fragments to a node under test, to determine how well that node reassembles the fragments.
The problem to be solved is how to generate unbiased random permutations of an arbitrary number of indices in hardware at a rate of at least one index per frame, which, assuming a minimum frame size of 64 bytes, 8 bytes preamble and 12 bytes gap, translates to one index per 16.8 ns in 40 Gbps networks and one every 6.72 ns at 100 Gbps. The indices so produced are used to construct and output packet fragments in random order. The number of fragments may range from 2 to 144 in a typical application.
These indices must (1) follow a uniform distribution and (2) ensure reasonable coverage. Because there are A144144=144!≅5.55·10249≅0.775·2830 ways of reordering 144 fragments, full coverage would require a seed space of 830 bits. Hardware having 830 bit wide data paths that can operate at the required frequency would be unwieldy and expensive. Hardware having a 32 bit wide data path is more common, but for a seed space size of 32 bits, the largest number of fragments for which full coverage is possible is F=12 fragments, which is much less than the needed 144.
Accordingly, in light of these disadvantages associated with conventional approaches to providing unbiased random permutations at full coverage, there exists a need for methods and systems for hardware generation of sequences that are statistically similar to a uniform random sample of all possible sequences. More specifically, there exists a need for a hardware implementation of uniform random shuffling.